package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/2 10:46
 *
 调整数组顺序使奇数位于偶数前面：
 1，两次遍历 时间O(n) 空间O(n)
 2,维护奇数个数i，如果遍历到后边的奇数，就把数组[id,i]向后移动 时间O(n^2) 空间O(n)
 */

public class Main4 {

    public int[] reOrderArray (int[] array) {
        //表示奇数应该插入的位置
        int id=0;
        for(int i=0;i<array.length;++i){
            if((array[i]&1)==1){
                int t=array[i];
                //将[id,j-1]向后移动然后插入id这个奇数
                for(int j=i;j>id;--j){
                    array[j]=array[j-1];
                }
                array[id++]=t;
            }
        }
        return array;
    }
    /*
    public int[] reOrderArray (int[] array) {
        int res[]=new int[array.length];
        int len=array.length;
        int id=0;
        for(int i=0;i<len;++i){
            if((array[i]&1)!=0){
                res[id++]=array[i];
            }
        }
        for(int i=0;i<len;++i){
            if((array[i]&1)==0){
                res[id++]=array[i];
            }
        }
        return res;
    }
    */
}
